package pers.qianyu.month_202012.date_20201221.LFU;

import java.util.*;

/**
 * 460. LFU 缓存
 * https://leetcode-cn.com/problems/lfu-cache/
 *
 * @author mizzle rain
 * @date 2020年12月21日20:53:07
 */
public class LFUCache {
    // 低效率方法
    private HashMap<Integer, Node> map = new HashMap<>();
    private LinkedList<Node> list = new LinkedList<>();
    private int cap;

    public LFUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        node.setFreq(node.getFreq() + 1);
        list.remove(node);
        list.add(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cap == 0) {
            return;
        }
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.setFreq(node.getFreq() + 1);
            node.setValue(value);
            return;
        }
        if (cap == list.size()) {
            remove();
        }
        Node node = new Node(key, value);
        list.add(node);
        map.put(key, node);
    }

    private void remove() {
        Node min = new Node(0, 0, Integer.MAX_VALUE);
        for (Node node : list) {
            if (min.getFreq() > node.getFreq()) {
                min = node;
            }
        }
        list.remove(min);
        map.remove(min.getKey());
    }

    static class Node {
        private int key;
        private int value;
        private int freq;

        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 0;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getFreq() {
            return freq;
        }

        public void setFreq(int freq) {
            this.freq = freq;
        }
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */